벨 수

1. 개요2. 성질3. 관련 문서

Bell number

1. 개요 [편집]

집합을 분할하는 방법의 수로, 원소의 개수가

n

인 집합을 분할하는 방법의 수를

n

번째 벨 수라고 하며

B_n

으로 나타낸다. 베르누이 수와 표기가 완전히 같기 때문에, 혼동을 피하기 위해 사용시에는 정의를 명확히 해줄 필요가 있다.
1930년대 이를 연구한 영국의 수학자 에릭 템플 벨의 이름을 따왔다.

제9항까지의 값은 다음과 같다.

$n$	$0$ [1]	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$
$B_n$	$1$	$1$	$2$	$5$	$15$	$52$	$203$	$877$	$4140$	$21147$

제2종 스털링 수 $S \left(n,~k \right)$ 와는 다음과 같은 관계가 있다.
$\displaystyle B_n = \sum_{k=0}^n S \left( n,~k \right)$
집합론을 이용한 제2종 스털링 수의 정의가 ‘ $n$ 개의 원소로 구성된 집합을 $k$ 개로 분할하는 경우의 수’이므로 위의 관계는 자명하다.

B_n

은 다음과 같은 점화식을 만족시킨다.

\displaystyle B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_k

집합

\left\{1,~2, \cdots\cdots ,~n+1 \right\}

을 분할한다고 하자. 이때 각각의 분할에서는

1

을 원소로 갖는 집합이 있을 것이다.

1

을 원소로 갖는 집합의 원소의 개수가

k

가 되도록 분할하는 경우의 수는

n

개 중에서

1

을 제외한

(k-1)

개를 고르는 경우의 수

\dbinom n{k-1}

에 나머지

n-(k-1)

개의 원소를 분할하는 경우의 수

B_{n-k+1}

를 곱한 값

\dbinom n{k-1} B_{n-k+1}

임을 알 수 있다.

k

는

1

부터

(n+1)

까지의 값을 취할 수 있고

k

가 다른 값을 취할 때 중복되는 경우는 없으므로 합의 법칙에 의하여

\displaystyle B_{n+1}=\sum_{k=1}^{n+1}\binom n{k-1}B_{n-k+1} = \sum_{k=0}^n \binom nk B_{n-k} = \sum_{k=0}^n \binom n{n-k}B_k = \sum_{k=0}^n \binom nk B_k

[1] '공집합을 분할'한다는 개념이 와닿지 않을 수 있으나, 대수적으로도 정의되는 제2종 스털링 수와의 관계에 따라

n=0

일 때에도 정의가 된다.

S \left( 0,~0 \right) = 1

이기 때문.